链接列表末尾的java插入节点
这类问题有一个简单的迭代解法
Node Insert(Node head,int data) {
Node newNode = new Node();
newNode.data = data;
if (head == null) {
return newNode;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
return head;
}
它工作得非常好。但我想学习递归,并从这个角度看问题。因此,我提出了下面的解决方案,它看起来很优雅,但我必须承认它只是直觉,给定的代码工作正常。我想开发一个使用递归的心智模型,或者至少用某种方法来验证我的代码是否可以正常工作。如何从理论上验证以下解决方案是否有效
递归版本
Node Insert(Node head,int data) {
// Base case.
if (head == null) {
Node newNode = new Node();
newNode.data = data;
return newNode;
}
// Smaller problem instance.
head.next = Insert(head.next, data);
return head;
}
# 1 楼答案
递归解决方案通常必须遵守以下规则:
if
)到两个代码块:基本块和通用块李>对于corse,这是一个简单的递归模型,实际上可能更复杂(不止一个基本情况,两个函数之间的递归,等等)
如果我们根据这些规则从理论上分析你的提案,我们可以看到它符合所有这些规则
# 2 楼答案
我会把代码再进一步,删除多个退出点。这使您可以推断对列表的影响以及返回哪个节点
就推理而言,你通常需要使用归纳法
list == null
),则创建一个新节点,它将成为您的列表李>鉴于上述情况,可以推断,在所有情况下,由于列表为空或不为空,该功能都将正常运行
在列表上使用递归通常被认为是低效且笨拙的,因为迭代算法更适合线性结构。更好的练习是编写自己的
Tree
结构,因为树非常适合递归算法。您会发现,在树上递归地执行所需的函数通常更容易、更优雅请注意,在
toString
方法中判断在何处添加“,”是多么简单,这是一个在打印列表时出了名的笨拙问题# 3 楼答案
假设你有5,3,2,1,你想加4,然后:-插入(节点(5),int 4)
if( node(5) == null )
然后head.next = node(5).next
这是node(3)
并调用Insert(node(3),4)
if( node(3) == null )
然后head.next = node(3).next
这是node(2)
并调用Insert(node(2),4)
if( node(2) == null )
然后head.next = node(2).next
这是node(1)
并调用Insert(node(1),4)
if( node(1) == null )
no thehead.next = node(1).next
这是null
,因为在node(1)
之后没有元素,所以调用Insert(node(1).next,4)
(node(1).next) == null
是,然后设置head = new node ();
并在结束返回头设置数据head = new node ();